§ 1.1 Field of the Invention
The present invention concerns an interface to stored information (e.g., a database), and in particular, concerns a natural language interface for generating queries to a database or database management system.
§ 1.2 Related Art
In recent decades, and in the past five to ten years in particular, computers have become interconnected by networks by an ever increasing extent; initially, via local area networks (or “LANs”), and more recently via wide area networks (or “WANs”) and the Internet. The proliferation of networks, in conjunction with the increased availability of inexpensive data storage means, has afforded computer users unprecedented access to a wealth of data. Unfortunately, however, the very vastness of available data can overwhelm a user; desired data can become difficult to find and search heuristics employed to locate desired data often return unwanted data.
Various concepts have been employed to help users locate desired data. In the context of the Internet for example, some services have organized content based on a hierarchy of categories. A user may then navigate through a series of hierarchical menus to find content that may be of interest to them. An example of such a service is the YAHOO™ World Wide Web site on the Internet. Unfortunately, content, in the form of Internet “web sites” for example, must be organized by the service and users must navigate through menus. If a user mistakenly believes that a category will be of interest or include what they were looking for, but the category turns out to be irrelevant, the user must backtrack through one or more hierarchical levels of categories.
Again in the context of the Internet for example, some services provide “search engines” which search databased content or “web sites” pursuant to a user query. In response to a user's query, a rank ordered list, which includes brief descriptions of the uncovered content, as well as a hypertext links (text, having associated Internet address information, which, when activated, commands a computer to retrieve content from the associated Internet address) to the uncovered content is returned. The rank ordering of the list is typically based on a match between words appearing in the query and words appearing in the content. Unfortunately, however, present limitations of search heuristics often cause irrelevant content to be returned in response to a query. Again, unfortunately, the very wealth of available content impairs the efficacy of these search engines since it is difficult to separate irrelevant content from relevant content.
Formal query languages, which include relatively simple declarative command query languages such as SQL (structured query language) for example, facilitate access to information stored in databases. Such formal command languages avoid ambiguities and are consequently easily interpreted by computer-based database management systems. Unfortunately, however, formal command query languages are difficult to learn and master, at least by non-computer specialists.
A form-based query interface may be used to ensure that queries are entered in canonical (i.e., unambiguous) form. A “query-by-example” interface is a more powerful form-based query interface. With a query-by-example database interface, a user can combine an arbitrary number of forms, where each form reflects the structure of a database table (or relation).
An example of a query-by-example database query interface is shown in the New York City SIDEWALK™ city guide Internet Website at “http://newyork.sidewalk.com/find a restaurant”, a portion of which is shown in FIG. 1. The query interface depicted in FIG. 1 includes five (5) field types (i.e., “neighborhood”, “cuisine type”, “price range”, “star rating” and “special option”) that are logically ANDed together to construct a query. Each of the five (5) field types may include a pull down menu that will be familiar to those who use “Windows 98” or Windows NT® operating systems sold by Microsoft Corporation of Redmond, Wash. Alternatively, information associated with a specific restaurant may be requested. FIGS. 2 and 3 depict similar form-based query-by-example interfaces for finding a movie and for finding a movie theater, respectively.
Although the form-based database query interfaces are fairly easy to use and intuitive, particularly for those familiar with pull down menus, the fact that they ensure proper entry of the query, by their nature, constrains their flexibility. For example, some believe that queries involving negation or quantification (e.g., “Which movies have no violent scenes?” or “Which movies are playing in every theater?”) are difficult to express using form-based query interfaces. Moreover, form-based (as well as formal) query interfaces are not particularly well suited for use with speech recognition input devices. Furthermore, users often would prefer to query a database in an even more intuitive method. The ultimate goal in this regard is to permit natural language database queries, such that database queries may be made in the same way people ask other people for information.
Thus, a goal of the present invention is to provide a natural language interface to stored (e.g., databased) information. The natural language interface to the stored information (e.g., a database) should be (i) easy, in terms of effort and expertise required, to author, and (ii) robust with respect to linguistic and conceptual variation (and consequently, easy to use). Each of these issues is addressed below.
More specifically, with respect to authoring, many natural language query interfaces require tedious and lengthy configuration phases before they can be used. Since many natural language query interfaces are designed for a particular database application, any authoring burdens will inhibit porting the natural language query interface to different applications. Thus, the authoring process of a natural language query interface should be relatively simple and quick so that the author need not be an expert and so that it can be easily ported to different applications.
With respect to robustness to linguistic and conceptual variations, a natural language query interface should meet a number of known challenges. Such challenges include modifier attachment ambiguities, quantifier scope ambiguities, conjunction and disjunction ambiguities, nominal compound ambiguities, anaphora, and elliptical sentences, each of which is briefly introduced below.
First, regarding modifier attachment ambiguities, a natural language query may include modifiers that modify the meaning of other syntactic constituents. For example, in the query “List all restaurants serving steak having excellent reviews”, it is unclear whether the modifier “having excellent reviews” attaches to “restaurants” or “steak”. The challenge is to identify the constituent to which each modifier has to be attached. In the past, semantic knowledge or heuristics were used in an attempt to resolve such ambiguities. Unfortunately, providing such semantic knowledge or heuristics increases the burden of authorizing such natural language query interfaces.
Regarding quantifier scope ambiguities, determiners like “a”, “each”, “all”, “some”, etc. are usually mapped to logic quantifiers. It may be difficult to determine the scope of such quantifiers. For example, in the query, “Has every movie received some award?”, either (a) each movie is allowed to have received different awards or (b) all movies must have received the same award. One known approach to resolving quantifier scope ambiguities is to prefer scopings preserving a left-to-right order of the quantifiers. Another known approach is to associate a numeric strength to each determiner.
Regarding conjunction and disjunction ambiguities, the word “and” can be used to denote disjunction or conjunction. For example, in the query “What people were born in Washington and Oregon?”, the “and” should probably be interpreted as an “or”. One known approach uses heuristics to determine cases in which it is conceptually impossible for “and” to denote conjunction and, in such cases, interprets “and” as “or”.
Regarding nominal compound ambiguities, in which a noun is modified by another noun or an adjective, it may be difficult to determine the meaning of such compounds. One known approach has required the meaning of each possible noun-noun or adjective-noun compound to be declared during a configuration of a natural language query interface. However, such an approach increases the complexity and tedium of the authoring process.
Anaphora describes a linguistic phenomenon in which pronouns, possessive determiners, and noun phrases are used to denote, implicitly, entities mentioned earlier in a discourse. For example, in query “Does it accept credit cards?”, the pronoun “it” refers to a previously introduced noun. For example, “it” may be interpreted as “the Four Seasons” if the preceding query was, “Is the Four Seasons restaurant expensive?”. A similar problem is presented by the use of incomplete (or elliptical) sentences, the meaning of which is inferred from a context of a discourse. For example, the elliptical query, “What about Oceana?” means “Does Oceana serve seafood” when it follows the query “Does the Four Seasons serve seafood?” Known natural language systems use a discourse model or contextual substitution rules to properly handle elliptical queries. Otherwise, to avoid the problems of anaphora and elliptical queries, the user would have to repeatedly type in the proper noun, possessive, etc. which can become annoying for the user.
Another challenge to natural language query interfaces is to make computer users comfortable with using them. Users may often improperly use natural language query interfaces because they might not be familiar with limitations of the natural language query interface. That is, they might not know how to construct a query, what they can ask for and they can't ask for. They may assume that a particular query may be processed that, in fact, cannot be processed (also referred to as a “false positive expectation”). On the other hand, they may assume that a particular query cannot be processed that, in fact, can be processed (also referred to as a “false negative expectation”). Moreover, if a query is not processed, it is often unclear to the user whether the query was beyond the system's linguistic capabilities or its conceptual capabilities. Such user uncertainty, and consequent discomfort, can lead to frustration, which may ultimately cause users to abandon a particular natural language query interface.
Thus, there is a need for a natural language query interface which can handle linguistic and contextual ambiguities while, at the same time, minimizing authoring burdens.